#include <iostream>
using namespace std; 
#include <vector>
#include <stack>
#include <list>


vector<vector<int>> MonotonicStack(vector<int>& arr);


vector<vector<int>> MonotonicStack(vector<int>& arr)
{
  int N = static_cast<int>(arr.size());
  vector<vector<int>> ans(N , vector<int>(2 , -1));

  stack<list<int>> st;

  for (int i = 0; i < N ; i++)
  {
    while(!st.empty() && arr[st.top().front()] > arr[i])
    {
      list<int> popIs = st.top();
      st.pop();

      int LeftIndex = st.empty() ? -1 : st.top().back();
      // 之后依次更新该链表中的所有位置 
      for (auto x : popIs)
      {
        ans[x][0] = LeftIndex;
        ans[x][1] = i;
      }
    }

    if (!st.empty() && arr[st.top().front()] == arr[i])
    {
      st.top().push_back(i);
    }
    else // empty ||  <   
    {
      list<int> Ins = {i};
      st.push(Ins);
    }
  }

  // 更新完毕之后可能栈里面还有值 也要全部更新完毕 最后返回ans
  while(!st.empty())
  {
    list<int> popIs = st.top();
    st.pop();

    int LeftIndex = st.empty() ? -1 : st.top().back();
    // 之后依次更新该链表中的所有位置 
    for (auto x : popIs)
    {
      ans[x][0] = LeftIndex;
      ans[x][1] = -1;
    }
  }

  return ans;
}



int main()
{
  vector<int> arr = {3 , 1, 1 ,3 , 5, 5, 5};

  vector<vector<int>> ans = MonotonicStack(arr);

  for(auto x : arr)
  {
    cout << x << " ";
  }

  cout << endl;
  for (auto x : ans)
  {
    for(auto y : x)
    {
      cout << y << " ";
    }
    cout << endl;
  }
}

